/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/counting-bits
   @Language: C++
   @Datetime: 19-05-08 15:46
   */


// Method 1, search table, Time 1711ms
class Solution {
public:
	/**
	 * @param num: a non negative integer number
	 * @return: an array represent the number of 1's in their binary
	 */
	vector<int> countBits(int num) {
		// write your code here
		int bits[1<<4]={0};
		for(int i=0; i<(1<<4); ++i){
			for(int a=i; a; a&=a-1)
				++bits[i];
		}
		vector<int> res(num+1,0);
		for(int i=0; i<=num; ++i){
			for(int a=i; a; a>>=4)
				res[i]+=bits[a&0xF];
		}
		return res;
	}
};


// Method 2, DP, Time 1661ms
class Solution {
public:
	/**
	 * @param num: a non negative integer number
	 * @return: an array represent the number of 1's in their binary
	 */
	vector<int> countBits(int num) {
		// write your code here
		vector<int> res(num+1,0);
		for(int i=1; i<=num; ++i)
			res[i]=res[i&(i-1)]+1;
		return res;
	}
};
